SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Learnable function class</title>

</head>

Learnable function class

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Statistical_learning_theory" title="Statistical learning theory">statistical learning theory</a>, a learnable function class is a <a href="Set_(mathematics)" title="Set (mathematics)">set</a> of <a href="Function_(mathematics)" title="Function (mathematics)">functions</a> for which an algorithm can be devised to asymptotically minimize the expected risk, uniformly over all probability distributions. The concept of learnable classes are closely related to <a href="Regularization_(mathematics)" title="Regularization (mathematics)">regularization</a> in <a href="Machine_learning" title="Machine learning">machine learning</a>, and provides large sample justifications for certain learning algorithms.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Background">Background</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">See also: <a href="Statistical_learning_theory" title="Statistical learning theory">Statistical learning theory</a></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega ={\mathcal {X}}\times {\mathcal {Y}}=\{(x,y)\}}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega ={\mathcal {X}}\times {\mathcal {Y}}=\{(x,y)\}}</annotation>

</semantics>

</math><img src="./44a0f956ab15215f005da3f770e2285de40c76a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.904ex; height:2.843ex;" alt="{\displaystyle \Omega ={\mathcal {X}}\times {\mathcal {Y}}=\{(x,y)\}}" loading="lazy"> be the sample space, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> are the labels and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> are the covariates (predictors). <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}=\{f:{\mathcal {X}}\mapsto {\mathcal {Y}}\}}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}=\{f:{\mathcal {X}}\mapsto {\mathcal {Y}}\}}</annotation>

</semantics>

</math><img src="./d93b78b7a6e09cdc341cd4882daaa7be6902d265.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.715ex; height:2.843ex;" alt="{\displaystyle {\mathcal {F}}=\{f:{\mathcal {X}}\mapsto {\mathcal {Y}}\}}" loading="lazy"> is a collection of mappings (functions) under consideration to link <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L:{\mathcal {Y}}\times {\mathcal {Y}}\mapsto \mathbb {R} }">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L:{\mathcal {Y}}\times {\mathcal {Y}}\mapsto \mathbb {R} }</annotation>

</semantics>

</math><img src="./1859202df586cdf005a6b5dea6684b6213c484fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.972ex; height:2.509ex;" alt="{\displaystyle L:{\mathcal {Y}}\times {\mathcal {Y}}\mapsto \mathbb {R} }" loading="lazy"> is a pre-given loss function (usually non-negative). Given a probability distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x,y)}</annotation>

</semantics>

</math><img src="./d5b3d8f37f5458c22b61eaf26e5af0523acb63e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.074ex; height:2.843ex;" alt="{\displaystyle P(x,y)}" loading="lazy"> on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega }</annotation>

</semantics>

</math><img src="./24b0d5ca6f381068d756f6337c08e0af9d1eeb6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Omega }" loading="lazy">, define the expected risk <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I_{P}(f)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{P}(f)}</annotation>

</semantics>

</math><img src="./b8afff568ff3e01625652c0648b2b08825dcfac6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.577ex; height:2.843ex;" alt="{\displaystyle I_{P}(f)}" loading="lazy"> to be:

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{P}(f)=\int L(f(x),y)dP(x,y)}</annotation>

</semantics>

</math><img src="./87408ffc9f0a2a6b24e8f71e4517edf80193bed4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:29.546ex; height:5.676ex;" alt="{\displaystyle I_{P}(f)=\int L(f(x),y)dP(x,y)}" loading="lazy"></dd></dl>

The general goal in statistical learning is to find the function in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}}</annotation>

</semantics>

</math><img src="./205d4b91000d9dcf1a5bbabdfa6a8395fa60b676.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.927ex; height:2.176ex;" alt="{\displaystyle {\mathcal {F}}}" loading="lazy"> that minimizes the expected risk. That is, to find solutions to the following problem:<a href="#cite_note-Vapnik2013-1">[1]</a>

<mover>

</mover>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {f}}=\arg \min _{f\in {\mathcal {F}}}I_{P}(f)}</annotation>

</semantics>

</math><img src="./e429668e5573af7b9dc2b07e88ad9ffa0c5b9182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:18.261ex; height:4.843ex;" alt="{\displaystyle {\hat {f}}=\arg \min _{f\in {\mathcal {F}}}I_{P}(f)}" loading="lazy"></dd></dl>

But in practice the distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> is unknown, and any learning task can only be based on finite samples. Thus we seek instead to find an algorithm that asymptotically minimizes the empirical risk, i.e., to find a sequence of functions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{{\hat {f}}_{n}\}_{n=1}^{\infty }}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{{\hat {f}}_{n}\}_{n=1}^{\infty }}</annotation>

</semantics>

</math><img src="./689d4356a11abb06b3a52d6f472d3092292cf883.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.561ex; height:3.509ex;" alt="{\displaystyle \{{\hat {f}}_{n}\}_{n=1}^{\infty }}" loading="lazy"> that satisfies

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lim _{n\rightarrow \infty }\mathbb {P} (I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)>\epsilon )=0}">

</mrow>

</munder>

</mrow>

<msub>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lim _{n\rightarrow \infty }\mathbb {P} (I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)>\epsilon )=0}</annotation>

</semantics>

</math><img src="./bea6f428dd9dea28a5c62766b8ee789168ab5af2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:35.577ex; height:4.843ex;" alt="{\displaystyle \lim _{n\rightarrow \infty }\mathbb {P} (I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)>\epsilon )=0}" loading="lazy"></dd></dl>

One usual algorithm to find such a sequence is through <a href="Empirical_risk_minimization" title="Empirical risk minimization">empirical risk minimization</a>.

<div class="mw-heading mw-heading3"><h3 id="Learnable_function_class">Learnable function class</h3></div>

We can make the condition given in the above equation stronger by requiring that the convergence is uniform for all probability distributions. That is:

/* start https://en.wikipedia.org/ */

.mw-parser-output table.numblk{border-collapse:collapse;border:none;margin-top:0;margin-right:0;margin-bottom:0}.mw-parser-output table.numblk>tbody>tr>td{vertical-align:middle;padding:0}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2){width:99%}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table{border-collapse:collapse;margin:0;border:none;width:100%}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:first-child,.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:last-child{padding:0 0.4ex}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:nth-child(2){width:100%;padding:0}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{padding:0}.mw-parser-output table.numblk>tbody>tr>td:last-child{font-weight:bold}.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child{font-weight:unset}.mw-parser-output table.numblk>tbody>tr>td:last-child::before{content:"("}.mw-parser-output table.numblk>tbody>tr>td:last-child::after{content:")"}.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child::before,.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child::after{content:none}.mw-parser-output table.numblk>tbody>tr>td{border:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td{border:thin solid}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td{border:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td{border:thin solid}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{border-left:none;border-right:none;border-bottom:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{border-left:thin solid;border-right:thin solid;border-bottom:thin solid}.mw-parser-output table.numblk:target{color:var(--color-base,#202122);background-color:#cfe8fd}@media screen{html.skin-theme-clientpref-night .mw-parser-output table.numblk:target{color:var(--color-base,#eaecf0);background-color:#301702}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output table.numblk:target{color:var(--color-base,#eaecf0);background-color:#301702}}

/* end https://en.wikipedia.org/ */

</style><table role="presentation" class="numblk" style="margin-left: 1.6em;"><tbody><tr><td class="nowrap"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lim _{n\rightarrow \infty }\sup _{P}\mathbb {P} (I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)>\epsilon )=0}">

</mrow>

</munder>

</mrow>

</munder>

</mrow>

<msub>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lim _{n\rightarrow \infty }\sup _{P}\mathbb {P} (I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)>\epsilon )=0}</annotation>

</semantics>

</math><img src="./56150a9ac5a50fe0484936825bc100908ea411b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:39.465ex; height:5.009ex;" alt="{\displaystyle \lim _{n\rightarrow \infty }\sup _{P}\mathbb {P} (I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)>\epsilon )=0}" loading="lazy"> </td> <td></td> <td class="nowrap">1</td></tr></tbody></table>

The intuition behind the more strict requirement is as such: the rate at which sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{{\hat {f}}_{n}\}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{{\hat {f}}_{n}\}}</annotation>

</semantics>

</math><img src="./2607606349f5206170684ce53823fba18822e067.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.242ex; height:3.343ex;" alt="{\displaystyle \{{\hat {f}}_{n}\}}" loading="lazy"> converges to the minimizer of the expected risk can be very different for different <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(x,y)}</annotation>

</semantics>

</math><img src="./d5b3d8f37f5458c22b61eaf26e5af0523acb63e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.074ex; height:2.843ex;" alt="{\displaystyle P(x,y)}" loading="lazy">. Because in real world the true distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> is always unknown, we would want to select a sequence that performs well under all cases.

However, by the <a href="No_free_lunch_theorem" title="No free lunch theorem">no free lunch theorem</a>, such a sequence that satisfies (<a href="#math_1">1</a>) does not exist if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}}</annotation>

</semantics>

</math><img src="./205d4b91000d9dcf1a5bbabdfa6a8395fa60b676.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.927ex; height:2.176ex;" alt="{\displaystyle {\mathcal {F}}}" loading="lazy"> is too complex. This means we need to be careful and not allow too "many" functions in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}}</annotation>

</semantics>

</math><img src="./205d4b91000d9dcf1a5bbabdfa6a8395fa60b676.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.927ex; height:2.176ex;" alt="{\displaystyle {\mathcal {F}}}" loading="lazy"> if we want (<a href="#math_1">1</a>) to be a meaningful requirement. Specifically, function classes that ensure the existence of a sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{{\hat {f}}_{n}\}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{{\hat {f}}_{n}\}}</annotation>

</semantics>

</math><img src="./2607606349f5206170684ce53823fba18822e067.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.242ex; height:3.343ex;" alt="{\displaystyle \{{\hat {f}}_{n}\}}" loading="lazy"> that satisfies (<a href="#math_1">1</a>) are known as learnable classes.<a href="#cite_note-Vapnik2013-1">[1]</a>

It is worth noting that at least for supervised classification and regression problems, if a function class is learnable, then the empirical risk minimization automatically satisfies (<a href="#math_1">1</a>).<a href="#cite_note-:0-2">[2]</a> Thus in these settings not only do we know that the problem posed by (<a href="#math_1">1</a>) is solvable, we also immediately have an algorithm that gives the solution.

<div class="mw-heading mw-heading2"><h2 id="Interpretations">Interpretations</h2></div>

If the true relationship between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\sim f^{*}(x)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\sim f^{*}(x)}</annotation>

</semantics>

</math><img src="./49752057de8ac204cafb8c5e5611560b31bda5b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.768ex; height:2.843ex;" alt="{\displaystyle y\sim f^{*}(x)}" loading="lazy">, then by selecting the appropriate loss function, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f^{*}}</annotation>

</semantics>

</math><img src="./190a73fde235865b8d2a783334f90194331c7f19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.375ex; height:2.676ex;" alt="{\displaystyle f^{*}}" loading="lazy"> can always be expressed as the minimizer of the expected loss across all possible functions. That is,

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f^{*}=\arg \min _{f\in {\mathcal {F}}^{*}}I_{P}(f)}</annotation>

</semantics>

</math><img src="./dc16c46d1ab674a6f91f5cbfe0a7cbe70c1c68b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:19.31ex; height:4.509ex;" alt="{\displaystyle f^{*}=\arg \min _{f\in {\mathcal {F}}^{*}}I_{P}(f)}" loading="lazy"></dd></dl>

Here we let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}^{*}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}^{*}}</annotation>

</semantics>

</math><img src="./89b9f90c78c7881f4dac9e4218cff561e5f869ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.058ex; height:2.343ex;" alt="{\displaystyle {\mathcal {F}}^{*}}" loading="lazy"> be the collection of all possible functions mapping <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {X}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {X}}}</annotation>

</semantics>

</math><img src="./8c7e5461c5286852df4ef652fca7e4b0b63030e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.875ex; height:2.176ex;" alt="{\displaystyle {\mathcal {X}}}" loading="lazy"> onto <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {Y}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {Y}}}</annotation>

</semantics>

</math><img src="./8935ef8cf454efa0b58363386c33f16a48ec36ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.659ex; height:2.509ex;" alt="{\displaystyle {\mathcal {Y}}}" loading="lazy">. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f^{*}}</annotation>

</semantics>

</math><img src="./190a73fde235865b8d2a783334f90194331c7f19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.375ex; height:2.676ex;" alt="{\displaystyle f^{*}}" loading="lazy"> can be interpreted as the actual data generating mechanism. However, the no free lunch theorem tells us that in practice, with finite samples we cannot hope to search for the expected risk minimizer over <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}^{*}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}^{*}}</annotation>

</semantics>

</math><img src="./89b9f90c78c7881f4dac9e4218cff561e5f869ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.058ex; height:2.343ex;" alt="{\displaystyle {\mathcal {F}}^{*}}" loading="lazy">. Thus we often consider a subset of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}^{*}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}^{*}}</annotation>

</semantics>

</math><img src="./89b9f90c78c7881f4dac9e4218cff561e5f869ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.058ex; height:2.343ex;" alt="{\displaystyle {\mathcal {F}}^{*}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}}</annotation>

</semantics>

</math><img src="./205d4b91000d9dcf1a5bbabdfa6a8395fa60b676.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.927ex; height:2.176ex;" alt="{\displaystyle {\mathcal {F}}}" loading="lazy">, to carry out searches on. By doing so, we risk that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f^{*}}</annotation>

</semantics>

</math><img src="./190a73fde235865b8d2a783334f90194331c7f19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.375ex; height:2.676ex;" alt="{\displaystyle f^{*}}" loading="lazy"> might not be an element of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}}</annotation>

</semantics>

</math><img src="./205d4b91000d9dcf1a5bbabdfa6a8395fa60b676.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.927ex; height:2.176ex;" alt="{\displaystyle {\mathcal {F}}}" loading="lazy">. This tradeoff can be mathematically expressed as

<msub>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mrow>

<msub>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mrow>

</mrow>

</munder>

<mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}^{*}}I_{P}(f)=\underbrace {I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)} _{(a)}+\underbrace {\inf _{f\in {\mathcal {F}}}I_{P}(f)-\inf _{f\in {\mathcal {F}}^{*}}I_{P}(f)} _{(b)}}</annotation>

</semantics>

</math><img src="./9aa467366561d469a7107660c446ca49e9dd927e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.338ex; margin-right: -0.028ex; width:68.001ex; height:8.843ex;" alt="{\displaystyle I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}^{*}}I_{P}(f)=\underbrace {I_{P}({\hat {f}}_{n})-\inf _{f\in {\mathcal {F}}}I_{P}(f)} _{(a)}+\underbrace {\inf _{f\in {\mathcal {F}}}I_{P}(f)-\inf _{f\in {\mathcal {F}}^{*}}I_{P}(f)} _{(b)}}" loading="lazy"> </td> <td></td> <td class="nowrap">2</td></tr></tbody></table>

In the above decomposition, part <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (b)}</annotation>

</semantics>

</math><img src="./659bf70e7fc2204493dc325b0e366f879723e111.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.807ex; height:2.843ex;" alt="{\displaystyle (b)}" loading="lazy"> does not depend on the data and is non-stochastic. It describes how far away our assumptions (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}}</annotation>

</semantics>

</math><img src="./205d4b91000d9dcf1a5bbabdfa6a8395fa60b676.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.927ex; height:2.176ex;" alt="{\displaystyle {\mathcal {F}}}" loading="lazy">) are from the truth (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}^{*}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}^{*}}</annotation>

</semantics>

</math><img src="./89b9f90c78c7881f4dac9e4218cff561e5f869ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.058ex; height:2.343ex;" alt="{\displaystyle {\mathcal {F}}^{*}}" loading="lazy">). <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (b)}</annotation>

</semantics>

</math><img src="./659bf70e7fc2204493dc325b0e366f879723e111.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.807ex; height:2.843ex;" alt="{\displaystyle (b)}" loading="lazy"> will be strictly greater than 0 if we make assumptions that are too strong (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}}</annotation>

</semantics>

</math><img src="./205d4b91000d9dcf1a5bbabdfa6a8395fa60b676.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.927ex; height:2.176ex;" alt="{\displaystyle {\mathcal {F}}}" loading="lazy"> too small). On the other hand, failing to put enough restrictions on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}}</annotation>

</semantics>

</math><img src="./205d4b91000d9dcf1a5bbabdfa6a8395fa60b676.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.927ex; height:2.176ex;" alt="{\displaystyle {\mathcal {F}}}" loading="lazy"> will cause it to be not learnable, and part <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a)}</annotation>

</semantics>

</math><img src="./a64873b3280e7364ad9047a172f57dbf009fa7d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.039ex; height:2.843ex;" alt="{\displaystyle (a)}" loading="lazy"> will not stochastically converge to 0. This is the well-known <a href="Overfitting" title="Overfitting">overfitting</a> problem in statistics and machine learning literature.

<div class="mw-heading mw-heading2"><h2 id="Example:_Tikhonov_regularization">Example: Tikhonov regularization</h2></div>

A good example where learnable classes are used is the so-called <a href="Tikhonov_regularization" class="mw-redirect" title="Tikhonov regularization">Tikhonov regularization</a> in <a href="Reproducing_kernel_Hilbert_space" title="Reproducing kernel Hilbert space">reproducing kernel Hilbert space</a> (RKHS). Specifically, let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F^{*}}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F^{*}}}}</annotation>

</semantics>

</math><img src="./c9c8efd4deaf1a4ef27ca689e063ec2941ab435d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.058ex; height:2.343ex;" alt="{\displaystyle {\mathcal {F^{*}}}}" loading="lazy"> be an RKHS, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ||\cdot ||_{2}}">

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ||\cdot ||_{2}}</annotation>

</semantics>

</math><img src="./64ff5d720eae541012abe05737a8f05eca61f957.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.321ex; height:2.843ex;" alt="{\displaystyle ||\cdot ||_{2}}" loading="lazy"> be the norm on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F^{*}}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F^{*}}}}</annotation>

</semantics>

</math><img src="./c9c8efd4deaf1a4ef27ca689e063ec2941ab435d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.058ex; height:2.343ex;" alt="{\displaystyle {\mathcal {F^{*}}}}" loading="lazy"> given by its inner product. It is shown in <a href="#cite_note-3">[3]</a> that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}=\{f:||f||_{2}\leq \gamma \}}">

</mrow>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}=\{f:||f||_{2}\leq \gamma \}}</annotation>

</semantics>

</math><img src="./801c45e098e2246357e8096e1a0b7f2ac21944fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.847ex; height:2.843ex;" alt="{\displaystyle {\mathcal {F}}=\{f:||f||_{2}\leq \gamma \}}" loading="lazy"> is a learnable class for any finite, positive <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma }</annotation>

</semantics>

</math><img src="./a223c880b0ce3da8f64ee33c4f0010beee400b1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.262ex; height:2.176ex;" alt="{\displaystyle \gamma }" loading="lazy">. The empirical minimization algorithm to the <a href="Duality_(mathematics)" title="Duality (mathematics)">dual form</a> of this problem is

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \arg \min _{f\in {\mathcal {F}}^{*}}\left\{\sum _{i=1}^{n}L(f(x_{i}),y_{i})+\lambda ||f||_{2}\right\}}</annotation>

</semantics>

</math><img src="./864c7f636e0ef9d3d0f7adf4a60d6d13593d1537.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:36.446ex; height:7.509ex;" alt="{\displaystyle \arg \min _{f\in {\mathcal {F}}^{*}}\left\{\sum _{i=1}^{n}L(f(x_{i}),y_{i})+\lambda ||f||_{2}\right\}}" loading="lazy"></dd></dl>

This was first introduced by Tikhonov<a href="#cite_note-TikhonovArsenin1977-4">[4]</a> to solve ill-posed problems. Many statistical learning algorithms can be expressed in such a form (for example, the well-known <a href="Ridge_regression" title="Ridge regression">ridge regression</a>).

The tradeoff between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a)}</annotation>

</semantics>

</math><img src="./a64873b3280e7364ad9047a172f57dbf009fa7d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.039ex; height:2.843ex;" alt="{\displaystyle (a)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (b)}</annotation>

</semantics>

</math><img src="./659bf70e7fc2204493dc325b0e366f879723e111.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.807ex; height:2.843ex;" alt="{\displaystyle (b)}" loading="lazy"> in (<a href="#math_2">2</a>) is geometrically more intuitive with Tikhonov regularization in RKHS. We can consider a sequence of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{{\mathcal {F}}_{\gamma }\}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{{\mathcal {F}}_{\gamma }\}}</annotation>

</semantics>

</math><img src="./5756c1a8fba749c9ab955dc98414af9b6ecf0b87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.121ex; height:3.009ex;" alt="{\displaystyle \{{\mathcal {F}}_{\gamma }\}}" loading="lazy">, which are essentially balls in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F^{*}}}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F^{*}}}}</annotation>

</semantics>

</math><img src="./c9c8efd4deaf1a4ef27ca689e063ec2941ab435d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.058ex; height:2.343ex;" alt="{\displaystyle {\mathcal {F^{*}}}}" loading="lazy"> with centers at 0. As <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma }</annotation>

</semantics>

</math><img src="./a223c880b0ce3da8f64ee33c4f0010beee400b1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.262ex; height:2.176ex;" alt="{\displaystyle \gamma }" loading="lazy"> gets larger, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}_{\gamma }}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}_{\gamma }}</annotation>

</semantics>

</math><img src="./36be95a0d54c1b27dfc8c97154d0f397b34c4b0e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.796ex; height:2.843ex;" alt="{\displaystyle {\mathcal {F}}_{\gamma }}" loading="lazy"> gets closer to the entire space, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (b)}</annotation>

</semantics>

</math><img src="./659bf70e7fc2204493dc325b0e366f879723e111.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.807ex; height:2.843ex;" alt="{\displaystyle (b)}" loading="lazy"> is likely to become smaller. However we will also suffer smaller convergence rates in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a)}</annotation>

</semantics>

</math><img src="./a64873b3280e7364ad9047a172f57dbf009fa7d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.039ex; height:2.843ex;" alt="{\displaystyle (a)}" loading="lazy">. The way to choose an optimal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma }</annotation>

</semantics>

</math><img src="./a223c880b0ce3da8f64ee33c4f0010beee400b1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.262ex; height:2.176ex;" alt="{\displaystyle \gamma }" loading="lazy"> in finite sample settings is usually through <a href="Cross-validation_(statistics)" title="Cross-validation (statistics)">cross-validation</a>.

<div class="mw-heading mw-heading2"><h2 id="Relationship_to_empirical_process_theory">Relationship to empirical process theory</h2></div>

Part <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a)}</annotation>

</semantics>

</math><img src="./a64873b3280e7364ad9047a172f57dbf009fa7d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.039ex; height:2.843ex;" alt="{\displaystyle (a)}" loading="lazy"> in (<a href="#math_2">2</a>) is closely linked to <a href="Empirical_process" title="Empirical process">empirical process</a> theory in statistics, where the empirical risk <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\sum _{i=1}^{n}L(y_{i},f(x_{i})),f\in {\mathcal {F}}\}}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\sum _{i=1}^{n}L(y_{i},f(x_{i})),f\in {\mathcal {F}}\}}</annotation>

</semantics>

</math><img src="./3f3b2341d424a54abdf328984397146b877b1245.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:24.729ex; height:6.843ex;" alt="{\displaystyle \{\sum _{i=1}^{n}L(y_{i},f(x_{i})),f\in {\mathcal {F}}\}}" loading="lazy"> are known as empirical processes.<a href="#cite_note-vaartWellner2013-5">[5]</a> In this field, the function class <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {F}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {F}}}</annotation>

</semantics>

</math><img src="./205d4b91000d9dcf1a5bbabdfa6a8395fa60b676.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.927ex; height:2.176ex;" alt="{\displaystyle {\mathcal {F}}}" loading="lazy"> that satisfies the stochastic convergence

</mrow>

</munder>

</mrow>

</mrow>

</munder>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sup _{P}\mathbb {E} \sup _{f\in {\mathcal {F}}}|\sum _{i=1}^{n}L(y_{i},f(x_{i}))-I_{P}(f)|=0}</annotation>

</semantics>

</math><img src="./6061e7549c0437c8edd894200bdcb318d2c5f8ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:39.398ex; height:6.843ex;" alt="{\displaystyle \sup _{P}\mathbb {E} \sup _{f\in {\mathcal {F}}}|\sum _{i=1}^{n}L(y_{i},f(x_{i}))-I_{P}(f)|=0}" loading="lazy"> </td> <td></td> <td class="nowrap">3</td></tr></tbody></table>

are known as uniform <a href="Glivenko%E2%80%93Cantelli_class" class="mw-redirect" title="Glivenko–Cantelli class">Glivenko–Cantelli classes</a>. It has been shown that under certain regularity conditions, learnable classes and uniformly Glivenko-Cantelli classes are equivalent.<a href="#cite_note-Vapnik2013-1">[1]</a> Interplay between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a)}</annotation>

</semantics>

</math><img src="./a64873b3280e7364ad9047a172f57dbf009fa7d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.039ex; height:2.843ex;" alt="{\displaystyle (a)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (b)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (b)}</annotation>

</semantics>

</math><img src="./659bf70e7fc2204493dc325b0e366f879723e111.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.807ex; height:2.843ex;" alt="{\displaystyle (b)}" loading="lazy"> in statistics literature is often known as the <a href="Bias-variance_tradeoff" class="mw-redirect" title="Bias-variance tradeoff">bias-variance tradeoff</a>.

However, note that in <a href="#cite_note-:0-2">[2]</a> the authors gave an example of stochastic convex optimization for General Setting of Learning where learnability is not equivalent with uniform convergence.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFVladimir_N._Vapnik2013" class="citation book cs1">Vladimir N. Vapnik (17 April 2013). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=EoDSBwAAQBAJ">The Nature of Statistical Learning Theory</a>. Springer Science & Business Media. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4757-2440-0</bdi>.</cite>

</li>

<li id="cite_note-:0-2">^ <a href="#cite_ref-:0_2-0">a</a> <a href="#cite_ref-:0_2-1">b</a> <cite class="citation journal cs1">"Learnability, stability and uniform convergence". The Journal of Machine Learning Research.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite class="citation journal cs1">"Learnability in Hilbert spaces with reproducing kernels". Journal of Complexity.</cite>

</li>

<li id="cite_note-TikhonovArsenin1977-4"><a href="#cite_ref-TikhonovArsenin1977_4-0">^</a> <cite id="CITEREFAndreĭ_Nikolaevich_TikhonovVasiliĭ_I︠A︡kovlevich_Arsenin1977" class="citation book cs1">Andreĭ Nikolaevich Tikhonov; Vasiliĭ I︠A︡kovlevich Arsenin (1977). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=ECrvAAAAMAAJ">Solutions of ill-posed problems</a>. Winston. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-470-99124-4</bdi>.</cite>

</li>

<li id="cite_note-vaartWellner2013-5"><a href="#cite_ref-vaartWellner2013_5-0">^</a> <cite id="CITEREFA.W._van_der_vaartJon_Wellner2013" class="citation book cs1">A.W. van der vaart; Jon Wellner (9 March 2013). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=zdDkBwAAQBAJ&pg=PA116">Weak Convergence and Empirical Processes: With Applications to Statistics</a>. Springer Science & Business Media. pp. 116–. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4757-2545-2</bdi>.</cite>

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2023-11-14" href="https://en.wikipedia.org/wiki/?title=Learnable_function_class&oldid=1185134191">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>